package com.leetcodehot.problems;

public class problems106 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int inleft = 0;
        int inright = inorder.length - 1;
        int postleft = 0;
        int postright = postorder.length - 1;
        return dfs(inorder, postorder, inleft, inright, postleft, postright);
    }

    private TreeNode dfs(int[] inorder, int[] postorder, int inleft, int inright, int postleft, int postright) {
        if (inleft > inright || postleft > postright) {
            return null;
        }
        TreeNode treeNode = new TreeNode(postorder[postright]);
        int x = postorder[postright];
        //第一步 查找x在inorder的位置
        int index = inleft;
        while (inorder[index] != x) {
            index++;
        }
        int nums = index - inleft;
        treeNode.left = dfs(inorder, postorder, inleft, index - 1, postleft, postleft + nums - 1);
        treeNode.right = dfs(inorder, postorder, index + 1, inright, postleft + nums, postright - 1);
        return treeNode;
    }
}
